Long-Term Evolution (LTE) is the next step in 3rd Generation (3G) cellular networks, which represents basically an evolution of the current mobile communications standards. The actual standard is known as the International Telecommunication Union (ITU) 3rd Generation Partnership Project (3GPP), Release 8, although the term LTE is often used to reference the standard. LTE is considered by many to be a Fourth Generation (4G) technology, both because it is faster than 3G, and because, like the Internet, LTE uses a flat “all-IP” architecture where all information, including voice, is handled as data. LTE provides throughputs up to 50 Mbps in uplink and up to 100 Mbps in downlink, uses scalable bandwidth from 1.25 to 20 MHz in order to suit the needs of network operators that have different bandwidth allocations and is also expected to improve spectral efficiency in networks, allowing carriers to provide more data and voice services over a given bandwidth.
Orthogonal Frequency Division Multiple Access (OFDMA) is specified as the downlink multiple access scheme in 3GPP LTE, which divides the available bandwidth into multiple narrow orthogonal frequency bands. For the uplink in LTE networks, Single-Carrier Frequency Division Multiple Access (SC-FDMA) is defined, which may be considered similar to OFDMA but with an additional Discrete-Fourier Transform that spreads the symbols prior to modulation and achieves a lower Peak-to-Average Power Ratio. Both OFDMA and SC-FDMA allow the base station (known as enhanced NodeB or eNodeB) in LTE networks to assign different “chunks” of time and frequency to the users in a cell.
In 3G and 4G networks there are several mechanisms by which the user equipment (UE) can inform the base station (e.g., NodeB or eNodeB) on the radio conditions and among the parameters used for this purpose, the quantity which is defined to measure the instantaneous quality of the radio conditions is called Channel Quality Indicator (CQI). The parameter CQI may refer to the whole bandwidth, or may be expressed as a set of values, each one referred to a different frequency subband in LTE.
One of the advantages of using OFDMA and SC-FDMA in the LTE radio interface is the possibility of supporting frequency selective scheduling (FSS) based on the CQI values reported by the UE to the eNodeB (through standardized procedures) and the estimations performed by the eNodeB (based on the sounding reference signals sent by the UE to assist the network in allocation of appropriate frequency resources for uplink transmission). The aim of any frequency selective scheduler is the optimal assignment of the available resources to the users in order to maximize the cell capacity of the wireless network as well as the throughput perceived by each user.
Due to the differences between uplink (UL) and downlink (DL), motivated by the different characteristics of OFDMA (used in DL) and SC-FDMA (used in UL), the scheduler must operate in a different way when dealing with DL and UL traffic. In downlink, the users may be assigned any combination of frequency subbands, but in uplink there is a contiguity constraint by which each user must be assigned a block of contiguous subcarriers. The scheduler must cope with the problem of obtaining optimal solutions for both strategies.
In OFDMA, the controllable radio resource has three aspects: frequency, time and space. A Physical Resource Block (PRB) is the basic time-frequency resource allocable for data transmission. The PRB is defined by 3GPP as a set of time frequency resources whose size is the minimum resource allocation size. Each so-called PRB is determined by its frequency extension (180 kHz) and its time extension (0.5 ms), and data are transmitted over one or more PRBs consisting of a set of contiguous sub-carriers and having a predefined time extension. Each subband comprises several PRBs.
The usual approach for scheduling of time and frequency resources is to decouple both dimensions, i.e. to make independent decisions in time and frequency so as to simplify the scheduling algorithm depicted in FIG. 1. In a first step (12) of the algorithm, which uses the reported CQI values as input (11) and results in scheduling pairs (16) formed by a user and its allocated subband, a number of users (13) is selected for time-domain scheduling in the next time interval (in LTE it is called TTI: Time Transmission Interval) or the minimum assignment interval. In a second step (14), a frequency-domain scheduling allocates PRBs or subbands (15) to the selected users (13). This method, described in US 2010165932 A1, has the problem of not optimizing time and frequency assignments simultaneously, so wrong scheduling decisions in the time domain may affect frequency domain scheduling. Besides, frequency domain scheduling is not optimal if restricted to only the subbands' frequency response of the previously selected users.
The LTE standard specifies that the scheduler (and the network entity usually in charge of resource scheduling in 3GPP systems is the base station, i.e., the eNodeB in LTE) is supposed to know all the CQI reports sent by the UEs on previous reports, and that these reports refer to the number of subbands. On a subframe basis, the scheduler running in the eNodeB first obtains a set of scheduling metrics for all the available combinations of pairs(user, subband), and then tries to find the optimal set of pairs so as to maximize the global cell throughput. A scheduling metric is a value used to select a UE and a particular subband for DL or UL scheduling. The metrics are then updated according to the scheduled resources for the next subframe. Such metrics may be based upon the Proportional Fair (PF) criterion, thus dividing the attainable throughput of each pair(user, subband) by the long-term average throughput of the users. This criterion takes into account each user's past history and tries not to benefit one user over another. Another possible criterion for the metrics may be to divide the throughputs by the long-term average resource use, measured as the number of subbands previously scheduled to the user.
Another solution for radio resource scheduling is disclosed in US 2009110087 A1, which discloses the use of threshold interference levels for identifying the subcarrier groups with interference below the current threshold interference level. This solution requires the estimation of threshold levels and, hence, there can be radio propagation conditions and situations for which this scheduling method cannot be accomplished.
US 20090296574 A1 describes another possible scheduling mechanism also referred as PFTF (Proportional Fair in Time and Frequency). PFTF is regarded as an extension of Proportional Fair criterion in the frequency domain, in which a chunk-wise scheduler makes independent decisions for each scheduling unit. This solution is not capable of assigning more than one scheduling unit for the same user. Moreover, it is not optimal, as the chunks are treated independently and no joint global solution is pursued.
On the other hand, mobile radio channels affect the transmitted signals introducing several degradations such as the time dispersion associated with the channel impulse response. This time dispersion comes from the fact that, at the receiver, several replicas of the original signal (called multipaths) are received with different amplitudes, delays and phases. These replicas interfere constructively or destructively depending on their relative phases, causing a frequency-selective degradation in the received signal. Therefore the received spectrum presents peaks and notches depending on the time dispersion of the channel. The peaks in the spectrum may be exploited by the scheduler, assigning users to those frequencies in which they are at better conditions, with the restriction of not assigning the same resources (time and frequency) to more than one user if it is operating in a single-input-single-output (SISO) antenna mode (i.e., one antenna for transmission and reception).
However, it is possible to find references to joint time-frequency scheduling algorithms, such as the one proposed in US 20090073926 A1. This algorithm describes an iterative “swapping” method that tries to find the optimal solution for assigning PRBs by provisionally assigning each PRB to the user having the corresponding highest metric and, then, looking at other PRBs and users previously assigned so that, if a higher throughput were obtained by exchanging any two PRBs and users, the swapping is performed. The procedure continues iteratively until all PRBs are assigned. This approach has the drawback that each user may be assigned only one PRB (and not any number, as is usually the case for real traffic). Especially when assigning contiguous frequency subbands to a single user, as is the case for LTE uplink, this solution is not suitable. In LTE downlink the users may be scheduled several non-localized frequency subbands, so it would neither be appropriate. Moreover, its complexity increases considerably with the number of PRBs, because for each new PRB one must pass the “swap” test over all previous assignments, and if a swap is performed between any two users, subsequent “swap checks” should be done against all users previously assigned.
Other existing solutions make some simplifications by assigning PRBs in an iterative way according to the CQI values, having the users ordered simply from best to worst values of CQI parameters. These approaches do not try to find the optimal solution, (indeed, an exact solution is very difficult to obtain, and in the case of uplink it is an NP-hard problem as stated by Lee et al. in the UCLA CSD TR-090001 “Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE uplink”, IEEE INFOCOM 2009), but they can serve as useful approximations with much lower complexity than a joint time and frequency scheduling algorithm.
Therefore, the objective is to find sub-optimal strategies for the scheduling, there being a trade-off between complexity and cell capacity improvement.